﻿#define _CRT_SECURE_NO_WARNINGS 1
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。
该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
int fib(int n){
	if (n == 0)
	{
		return 0;
	}
	if (n == 1)
	{
		return 1;
	}
	else if (n == 2)
	{
		return 1;
	}
	int a = 1;
	int b = 1;
	int c = 0;
	for (int i = 2; i<n; i++)
	{
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}







给你一个 m x n 的矩阵，最开始的时候，每个单元格中的值都是 0。

另有一个二维索引数组 indices，indices[i] = [ri, ci] 指向矩阵中的某个位置，其中 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。

对 indices[i] 所指向的每个位置，应同时执行下述增量操作：

ri 行上的所有单元格，加 1 。
ci 列上的所有单元格，加 1 。
给你 m、n 和 indices 。请你在执行完所有 indices 指定的增量操作后，返回矩阵中 奇数值单元格 的数目。

来源：力扣（LeetCode）
链接：https ://leetcode-cn.com/problems/cells-with-odd-values-in-a-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
int oddCells(int n, int m, int** indices, int indicesSize, int* indicesColSize){
	int grid[n][m];
	memset(grid, 0, sizeof grid);

	for (int i = 0; i < indicesSize; ++i) {
		const int r = *(*(indices + i));
		const int c = *(*(indices + i) + 1);
		for (int x = 0; x < m; ++x) ++grid[r][x];
		for (int y = 0; y < n; ++y) ++grid[y][c];
	}

	int ans = 0;
	for (int y = 0; y < n; ++y)
		for (int x = 0; x < m; ++x)
			ans += *(*(grid + y) + x) & 1;

	return ans;
}








给你一个按 YYYY - MM - DD 格式表示日期的字符串 date，请你计算并返回该日期是当年的第几天。

通常情况下，我们认为 1 月 1 日是每年的第 1 天，1 月 2 日是每年的第 2 天，依此类推。每个月的天数与现行公元纪年法（格里高利历）一致。

来源：力扣（LeetCode）
链接：https ://leetcode-cn.com/problems/day-of-the-year
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
int dayOfYear(char * date){
	int n = 0;
	int y = 0;
	int r = 0;
	int day[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
	int i = 0;
	int count = 0;
	for (i = 0; i<4; i++)
	{
		n = n * 10 + (date[i] - '0');
	}
	for (i = 5; i<7; i++)
	{
		y = y * 10 + (date[i] - '0');
	}
	for (i = 8; i<10; i++)
	{
		r = r * 10 + (date[i] - '0');
	}
	if (n % 4 == 0 && n % 100 != 0 || n % 400 == 0)
	{
		day[1] = 29;
	}
	for (i = 0; i<y - 1; i++)
	{
		count += day[i];
	}
	count += r;
	return count;
}







给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25 % 。

请你找到并返回这个整数
int findSpecialInteger(int* arr, int arrSize){
	for (int *p = arr, *q = arr + arrSize / 4;; p++, q++)
	{
		if (*q == *p)
		{
			return *p;
		}
	}
	return 0;
}








给定 N 个无限容量且初始均空的水缸，每个水缸配有一个水桶用来打水，第 i 个水缸配备的水桶容量记作 bucket[i]。小扣有以下两种操作：

升级水桶：选择任意一个水桶，使其容量增加为 bucket[i] + 1
蓄水：将全部水桶接满水，倒入各自对应的水缸
每个水缸对应最低蓄水量记作 vat[i]，返回小扣至少需要多少次操作可以完成所有水缸蓄水要求。

注意：实际蓄水量 达到或超过 最低蓄水量，即完成蓄水要求。

来源：力扣（LeetCode）
链接：https ://leetcode-cn.com/problems/o8SXZn
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
int max(int a, int b) {
	return a > b ? a : b;
}

int min(int a, int b) {
	return a < b ? a : b;
}

int storeWater(int *bucket, int bucketSize, int *vat, int vatSize) {
	if (bucketSize != vatSize) {
		return 0;
	}
	// 1 <= bucket.length == vat.length <= 100
	int vmax = vat[0];
	for (int i = 1; i < vatSize; i++) {
		if (vat[i] > vmax) {
			vmax = vat[i];
		}
	}
	if (!vmax) {
		return 0;
	}
	int res = 2147483647;
	int sum, needs, times;
	for (int i = 1; i < vmax + 1; i++) {
		sum = i;
		for (int j = 0; j < bucketSize; j++) {
			needs = ceil((double)vat[j] / i);
			times = max(0, needs - bucket[j]);
			sum += times;
		}
		res = min(res, sum);
	}
	return res;
}









//小扣打算给自己的 VS code 安装使用插件，初始状态下带宽每分钟可以完成 1 个插件的下载。假定每分钟选择以下两种策略之一:
//使用当前带宽下载插件
//将带宽加倍（下载插件数量随之加倍）
//请返回小扣完成下载 n 个插件最少需要多少分钟。
//注意：实际的下载的插件数量可以超过 n 个
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/Ju9Xwi
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int leastMinutes(int n){
//	int i = 1;
//	int cur = 0;
//	int time = 0;
//	while (cur<n)
//	{
//		if (i * 2<n)
//		{
//			i *= 2;
//		}
//		else
//		{
//			cur += i;
//		}
//		time++;
//	}
//	return time;
//}







/**有一个同学在学习分式。他需要将一个连分数化成最简分数，你能帮助他吗？
连分数是形如上图的分式。在本题中，所有系数都是大于等于0的整数。
输入的cont代表连分数的系数（cont[0]代表上图的a0，以此类推）。返回一个长度为2的数组[n, m]，使得连分数的值等于n / m，且n, m最大公约数为1。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/deep-dark-fraction
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* Note: The returned array must be malloced, assume caller calls free().
*/
//int* fraction(int* cont, int contSize, int* returnSize){
//	*returnSize = 2;
//	int* ret = (int*)malloc(sizeof(int) * 2);
//	ret[0] = cont[contSize - 1];
//	ret[1] = 1;
//	if (contSize == 1)
//	{
//		return ret;
//	}
//	int n, m;
//	for (int i = contSize - 2; i >= 0; i--)
//	{
//		n = ret[1] + cont[i] * ret[0];
//		m = ret[0];
//		ret[0] = n;
//		ret[1] = m;
//	}
//	return ret;
//}







//两个数对 (a, b) 和(c, d) 之间的 乘积差 定义为(a * b) - (c * d) 。
//例如，(5, 6) 和(2, 7) 之间的乘积差是(5 * 6) - (2 * 7) = 16 。
//给你一个整数数组 nums ，选出四个 不同的 下标 w、x、y 和 z ，使数对(nums[w], nums[x]) 和(nums[y], nums[z]) 之间的 乘积差 取到 最大值 。
//返回以这种方式取得的乘积差中的 最大值 。
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/maximum-product-difference-between-two-pairs
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//int maxProductDifference(int* nums, int numsSize){
//	for (int i = 0; i<numsSize - 1; i++)
//	{
//		for (int j = i + 1; j<numsSize; j++)
//		{
//			if (nums[i]>nums[j])
//			{
//				int tmp = nums[i];
//				nums[i] = nums[j];
//				nums[j] = tmp;
//			}
//		}
//	}
//	int w = nums[0];
//	int x = nums[1];
//	int y = nums[numsSize - 1];
//	int z = nums[numsSize - 2];
//	int max = (y*z) - (w*x);
//	return max;
//}








//给你一个下标从 0 开始的整数数组 nums ，如果 恰好 删除 一个 元素后，数组 严格递增 ，那么请你返回 true ，否则返回 false 。如果数组本身已经是严格递增的，请你也返回 true 。
//
//数组 nums 是 严格递增 的定义为：对于任意下标的 1 <= i < nums.length 都满足 nums[i - 1] < nums[i] 。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/remove-one-element-to-make-the-array-strictly-increasing
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//bool canBeIncreasing(int* nums, int numsSize){
//	int count = 0;
//	for (int i = 1; i<numsSize; i++)
//	{
//		if (nums[i] <= nums[i - 1])
//		{
//			if (i>1 && nums[i] <= nums[i - 2])
//			{
//				nums[i] = nums[i - 1];
//			}
//			count++;
//			if (count>1)
//			{
//				return false;
//			}
//		}
//	}
//	return true;
//}







//小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：
//有 n 名玩家，所有玩家编号分别为 0 ～ n - 1，其中小朋友 A 的编号为 0
//每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。
//每轮信息必须需要传递给另一个人，且信息可重复经过同一个人
//给定总玩家数 n，以及按[玩家编号, 对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A(编号 0) 经过 k 轮传递到编号为 n - 1 的小伙伴处的方案数；若不能到达，返回 0。
//int numWays(int n, int** relation, int relationSize, int* relationColSize, int k){
//	int row = k + 1;
//	int col = n;
//	int dp[row][col];
//	memset(dp, 0, sizeof(dp));
//	int i = 0;
//	int j = 0;
//	dp[0][0] = 1;
//	for (i = 1; i<row; i++)
//	{
//		for (j = 0; j<relationSize; j++)
//		{
//			dp[i][relation[j][1]] += dp[i - 1][relation[j][0]];
//		}
//	}
//	return dp[k][n - 1];
//}